package codes.sketch.quicksort;

public class Ordering {

    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int first, int last) {
        if (first < last) {
            int left = first;
            int right = last;
            int median = arr[(left + right) / 2];
            do {
                while (arr[left] < median) {
                    left++;
                }
                while (arr[right] > median) {
                    right--;
                }
                if (left <= right) {
                    int tmp = arr[left];
                    arr[left] = arr[right];
                    arr[right] = tmp;
                    left++;
                    right--;
                }
            } while (left < right);

            quickSort(arr, first, right);  //sort left part
            quickSort(arr, left, last);    //sort right part
        }
    }
}
